package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhangjy
 * @description 合并二叉树
 * @date 2025/4/22 19:36
 */
public class MergeTrees_617 {

    /**
     * 官解：dfs-迭代-先序
     */
    public TreeNode mergeTrees4(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        TreeNode merged = new TreeNode(root1.val + root2.val);
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
        queue.offer(merged);
        queue1.offer(root1);
        queue2.offer(root2);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node = queue.poll(), node1 = queue1.poll(), node2 = queue2.poll();
            TreeNode left1 = node1.left, left2 = node2.left, right1 = node1.right, right2 = node2.right;
            if (left1 != null || left2 != null) {
                if (left1 != null && left2 != null) {
                    TreeNode left = new TreeNode(left1.val + left2.val);
                    node.left = left;
                    queue.offer(left);
                    queue1.offer(left1);
                    queue2.offer(left2);
                } else if (left1 != null) {
                    node.left = left1;
                } else if (left2 != null) {
                    node.left = left2;
                }
            }
            if (right1 != null || right2 != null) {
                if (right1 != null && right2 != null) {
                    TreeNode right = new TreeNode(right1.val + right2.val);
                    node.right = right;
                    queue.offer(right);
                    queue1.offer(right1);
                    queue2.offer(right2);
                } else if (right1 != null) {
                    node.right = right1;
                } else {
                    node.right = right2;
                }
            }
        }
        return merged;
    }

    /**
     * 个解：dfs-迭代
     * <p>
     * 思路：
     * 1.先序遍历（有问题，参考官解）；
     * 2.层序遍历（未做）。
     */
    public TreeNode mergeTrees3(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        Queue<TreeNode> queue = new LinkedList<>();
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        // 新二叉树
        TreeNode root = new TreeNode(root1.val + root2.val);
        queue.offer(root);
        queue1.offer(root1);
        queue2.offer(root2);
        while (!queue1.isEmpty() || !queue2.isEmpty()) {
            TreeNode node = queue.poll(), node1 = queue1.poll(), node2 = queue2.poll();
            TreeNode node1Left = node1.left, node1Right = node1.right;
            TreeNode node2Left = node2.left, node2Right = node2.right;
            // 记录当前节点的左子树（因为）
            if (node1Left != null || node2Left != null) {
                TreeNode left = null;
                if (node1Left != null && node2Left != null) {
                    left = new TreeNode(node1Left.val + node2Left.val);
                    queue1.offer(node1Left);
                    queue2.offer(node2Left);
                } else if (node1Left != null) {
                    left = node1Left;
                    queue1.offer(node1Left);
                } else {
                    left = node2Left;
                    queue2.offer(node1Left);
                }
                // 记录得到的新节点
                queue.offer(left);
                node.left = left;
            }
            // 记录当前节点的右子树
            if (node1Right != null || node2Right != null) {
                TreeNode right = null;
                if (node1Right != null && node2Right != null) {
                    right = new TreeNode(node1Right.val + node2Right.val);
                    queue1.offer(node1Right);
                    queue2.offer(node2Right);
                } else if (node1Right != null) {
                    right = node1Right;
                    queue1.offer(node1Right);
                } else {
                    right = node2Right;
                    queue2.offer(node2Right);
                }
                // 记录得到的新节点
                queue.offer(right);
                node.right = right;
            }
        }

        return root;
    }

    /**
     * 参考dmsxl：dfs-递归-先序
     * <p>
     * 优化思路：不新建节点，直接在root1或root2上改造得到新二叉树。
     */
    public TreeNode mergeTrees2(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        // 中
        // 都不空，节点值累加
        root1.val += root2.val;
        // 左
        TreeNode left = mergeTrees(root1.left, root2.left);
        // 右
        TreeNode right = mergeTrees(root1.right, root2.right);
        root1.left = left;
        root1.right = right;

        return root1;
    }

    /**
     * 个解：dfs-递归-先序
     * <p>
     * T(n) = O(n)；其中，n为节点个数，每个节点只递归一次。
     * S(n) = O(n)；其中，n为节点个数。
     */
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 都为空的时候，第一个root1==null就会return null，因为 root2为null。
//        if (root1 == null && root2 == null) return null;
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        // 根
        int nodeVal = root1.val + root2.val;
        TreeNode node = new TreeNode(nodeVal);

        // 左
        TreeNode left = mergeTrees(root1.left, root2.left);
        // 右
        TreeNode right = mergeTrees(root1.right, root2.right);
        node.left = left;
        node.right = right;

        return node;
    }

}
